Leetcode-Implement strStr()

发表于 | 分类于 |

Implement strStr()

从字符串中找出给定子字符串的索引，若不存在则返回-1。
Description

解题思路：
用python解决这道题很简单，因为python字符串自带的find的方法可以直接实现。

1
2
3
4
5
6
7
def strStr(self, haystack, needle):
    """
    :type haystack: str
    :type needle: str
    :rtype: int
    """
    return haystack.find(needle)

不采用find()方法的解题思路：
采用brute force方式，即依次从字符串的每个位置开始，截取和子字符串相同长度的字符串，与给定的子字符串进行比较。

1
2
3
4
5
6
7
8
9
10
def strStr(self, haystack, needle):
    """
    :type haystack: str
    :type needle: str
    :rtype: int
    """ 
    for i in range(len(haystack)-len(needle)+1):
        if haystack[i:i+len(needle)] == needle:
            return i
    return -1

改进：http://blog.csdn.net/linhuanmars/article/details/20276833
提出了一种rolling hash的方式。